1. Field of the Invention
This invention relates to testing of network routers, particularly for compliance with Internet routing protocols.
2. Discussion of the Known Art
The Internet is a packet-switched network that enables linked host computers to exchange information in the form of packets. When information packets are transmitted from a source node to a destination node via the network, routing decisions are made by special purpose computers called Internet protocol (IP) routers. The routers are connected using a variety of linking media including, e.g., telephone lines, Ethernet segments, satellite links, ATM and FDDI.
To route packets correctly and efficiently, routers must follow a set of rules known as routing protocols. See C. Huitema, Routing in the Internet, Prentice-Hall (1995). Typical protocols used for Internet traffic include Routing Information Protocol (RIP) Open Shortest Path First (OSPF) and Border Gateway Protocol (BGP). See C. Hedrick, RFC 1058, the Internet Engineering Task Force (June 1988); J. T. Moy, OSPFxe2x80x94Anatomy of an Internet Routing Protocol, Addison-Wesley (1998); and Y. Rekhter, et al., RFC 1771, Internet Engineering Task Force (March 1995). While there are no precise specifications for these routing protocols, there are commonly expected invariant behaviors for routers such as (1) compiling a correct routing table, (2) proper packet forwarding, and (3) accumulating correct network topology information. Thus, it is important to test whether or not a given router will operate as expected in a network where it is to be deployed.
Internet usage is increasing rapidly. Sophisticated functions and services, such as service differentiation, quality-of-service (QoS) routing, multi casting, and World Wide Web are introduced on a regular basis. Because the design and implementation of routing protocols in such an environment are complex, proper testing of routers to be used on the Internet under a given protocol, is indispensable.
Typical systems and tools for detecting IP router faults, may be classified either as passive monitoring tools or as active testing tools. An approach used by most monitoring tools such as xe2x80x9cRouteMonitorxe2x80x9d works as follows. A collection of monitoring devices are deployed in an existing network to observe traffic exchanged between network routers. The devices are passive in that they do not inject route updates into the network. Based on observed routing information, the devices imitate the operation of a real router, execute a given routing protocol, and compute a routing table. Faults are then found by comparing the computed routing tables with an analysis of statistics for each route in the routing table. See D. Massey, et al, Fault Detection in Routing Protocols, Proceeding of International Conference on Network Protocols, pages 31-40 (1999).
Active testing is more effective for fault detection. Available commercial tools include Qosnetics QA Robot and Midnight ANVIL. See Qosnetics, QA robot, (now Agilent Technologies, Inc., Palo Alto, Calif.) (2000); and Midnight Networks, Anvil, (now Empirix, Waltham, Mass.). These tools generate a set of tests for xe2x80x9ctypicalxe2x80x9d network configurations or topologies. Because it is not feasible computationally to consider all possible network configurations, existing tools consider only a small subset of possible configurations. Moreover, this subset is chosen in an ad-hoc manner. Thus, even if a router passes all tests using a current tool, there remains a lack of statistical confidence in any judgment rendered by the tool.
According to the invention, a method of testing a network router for operation according to a given protocol, includes coupling a router under test (RUT) to a test host device, and configuring the device to simulate a network having at most a given number of router nodes and at most a given number of network nodes with edges connecting the router and the network nodes to one another. The host device sends information packets to and receives information packets from the RUT for each of a number of test network topologies under the given protocol. Each test network topology is determined by inserting or deleting an edge or a node to or from a prior test network topology in a probabilistic manner. Operation of the RUT is evaluated with respect to at least one of routing table compilation, packet forwarding, and network topology information accumulated by the RUT. A judgment concerning operation of the RUT under the given protocol is then rendered.